package lyl.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

public class TopK {
    static class Point {
        int x;
        int y;
        Point() {
            x = 0;
            y = 0;
        }
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) {
        Point[] points = new Point[5];
        Point point1 = new Point(4,6);
        Point point2 = new Point(4,7);
        Point point3 = new Point(4,4);
        Point point4 = new Point(2,5);
        Point point5 = new Point(1,1);
        Point origin = new Point(0,0);
        points[0] = point1;
        points[1] = point2;
        points[2] = point3;
        points[3] = point4;
        points[4] = point5;
        Point[] result = kClosest(points, origin, 3);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i].x + " ");
            System.out.print(result[i].y);
            System.out.println();
        }
    }
    private static Point global_origin = null;
    public static Point[] kClosest(Point[] points, Point origin, int k) {

        global_origin = origin;
        PriorityQueue<Point> pq = new PriorityQueue<Point>(k, new Comparator<Point>() {
            public int compare(Point p1, Point p2) {
                int diff = getDistance(p2, global_origin) - getDistance(p1, global_origin);
                if (diff == 0) {
                    diff = p2.x - p1.x;
                }
                if (diff == 0) {
                    diff = p2.y - p1.y;
                }

                return diff;
            }
        });

        for (int i = 0; i < points.length; i++) {
            pq.offer(points[i]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        k = pq.size();
        Point[] result = new Point[k];
        while (!pq.isEmpty()) {
            result[--k] = pq.poll();
        }
        return result;
    }

    public static int getDistance(Point p1, Point p2) {
        //勾股定理
        return 0;
    }
}
